package org.apache.test.suanfa;

import java.util.ArrayList;
import java.util.List;

//https://www.cnblogs.com/sunniest/p/4596182.html
/**http://blog.51cto.com/12176710/1963175
 * https://blog.csdn.net/Arnold_lee_yc/article/details/76851239
 * https://www.jianshu.com/p/d1f8b9d6ad57
 * Created by hanlin.huang on 2018/7/11.
 */
public class Subject2 {


    public static void main(String[] args){
        Subject2 t = new Subject2();
        t.test();
    }


    public void test(){
        int[] num = {1,2,2,3,4,5,6,7,8,9};
        int sum = 17;
        System.out.println(findContinueNumberForSum(num, sum, null));
    }

    private List<String> findContinueNumberForSum(int[] num, int sum,List<String> list) {
        if(!(num.length>0)) return list;
        if(list == null){
            list = new ArrayList<String>();
        }
        for(int i=0;i<num.length;i++){
           if(num[i]>sum){
                return list;
           }
           if(num[i] == sum){
               list.add(num[i]+"");
               return list;
           }
           int[] num1 = new int[num.length-i-1];
           for(int q=0;q<num.length-i-1;q++){
                num1[q] = num[(q+i)+1];
           }

           if(num[i]<sum) {
               List<String> l = new ArrayList<String>();
               l.add(num[i]+"");
               List<String> result = getThisSum(l, num[i], num1, sum);
               if(result != null && result.size()>0){
                   list.add(result.toString());
               }
           }
        }
        return list;
    }

    private List<String> getThisSum(List<String> list,int beforeNumber, int[] num1, int sum) {

        if(list == null) {
            list = new ArrayList<String>();
        }

        for(int i=0;i<num1.length;i++){
            beforeNumber += num1[i];
            if(beforeNumber > sum){
                return null;
            }
            if(beforeNumber == sum){
                list.add(num1[i]+"");
                return list;
            }
            if(beforeNumber < sum){
                list.add(num1[i]+"");
                int[] num2 = new int[num1.length-1];
                for(int k=0;k<num1.length-1;k++){
                    num2[k] = num1[k+1];
                }
                return getThisSum(list, beforeNumber, num2, sum);
            }
        }

        return null;
    }






}
